There is significant interest in reliably sending digital data over narrow band channels such as voice-band telephone lines at the highest possible rates. The highest rate current international standards for voice-band modems are the CCITT V.32 bis and V.33 standards for transmission at 14.4 kilo bits per second (kbps) with prospective standards calling for rates up to at least 24 kbps. Some nonstandard commercial modems that achieve this high rate on some channels are currently available. However, to achieve higher data rates, the modems use more of the available bandwidth of the channel and employ signal constellations with more points. The wider bandwidth transmitted signals are more severely distorted by the voice-band channels which cause both severe amplitude response rolloff and envelope delay distortion at the lower and upper band edges. The result, in the time-domain, of these deficiencies is an increase in intersymbol interference (ISI). In addition, a signal constellation with more points is adversely affected by additive noise and nonlinearity in the channel. Currently existing and some proposed high speed modems use complicated channel trellis codes and trellis precoding/shaping. These techniques require higher computational resources in the hardware and also lack some flexibility in choosing a variety of data rates.
Constellation shaping refers to methods that reduce the transmitted signal power for a fixed minimum distance between constellation points. This technique allows more reliable data transmission over channels corrupted by additive noise. The trellis precoding/shaping technique mentioned in the previous paragraph is currently employed in some commercial modems. The structured vector quantizer (SVQ) shaping method described below can achieve superior shaping gain at the same complexity of the trellis precoding/shaping method. Also, the SVQ technique can easily incorporate constraints on the constellation peak-to-average ratio with almost no loss of shaping gain. Furthermore, the SVQ technique can easily accommodate flexible data rates.
Precoding is used in transmitters to compensate for distortion introduced by the channel response and/or noise whitening filters used in the modem receivers. The precoding method disclosed below is significantly simpler to implement than the trellis precoding technique and can be used with a variety of shaping methods without destroying the shaping gain. The combination of constellation shaping and precoding reduces the effects of intersymbol interference and noise enhancement and allows for more reliable data transmission at high data rates.
High speed modems use more of the available channel bandwidth, that is, have wider bandwidth transmitted signals, because they must use a higher symbol (baud) rate. This leads to more ISI because the spectrum of the transmitted signal extends into the channel band edges where amplitude attenuation and envelope delay distortion become severe. To compensate for this channel distortion, a linear equalizer can be used at the channel output. But, by boosting the band edges, the equalizer enhances and correlates the noise. Alternatively, decision feedback equalization (DFE) can be used to eliminate ISI without noise enhancement. When used in coded modulation systems, DFE results in high complexity decoding techniques as discussed in M. V. Eyuboglu and S. U. H. Qureshi, "Reduced-State Sequence Estimation for Coded Modulation on Intersymbol Interference Channels," IEEE J. Select. Areas Commun, Vol. 7, pp. 989-995, August 1989. Tomlinson-Harashima precoding as discussed in M. Tomlinson, "NeW Automatic Equalizer Employing Modulo Arithmetic," Electron. Lett., Vol. 7, pp. 138-139, March 1971, and H. Harashima and H. Miyakawa, "Matched-Transmission Technique for Channels with Intersymbol Interference," IEEE Trans. Commun., Vol. 30, pp. 774-780, August 1972, equalizes the signal before transmission, is relatively simple to implement and can be used with coded modulation. However, this precoding scheme does not realize any shaping gain that results from having a spherical constellation boundary rather than a cubic boundary. Recently, Eyuboglu and Forney ("Trellis Precoding: Combined Coding, Precoding and Shaping for Intersymbol Interference Channels," IEEE Trans. Inform. Theory, Vol. 38, pp. 301-314, March 1992) have proposed a trellis precoding scheme that whitens the noise at the equalizer output. This scheme combines precoding and trellis shaping (G. D. Forney, Jr., "Trellis Shaping," IEEE Trans. Inform. Theory, Vol. 38, pp. 281-300, March 1992) and achieves 0.7-0.9 dB shaping gain with a 4-state trellis. However, there are, drawbacks of trellis precoding which include: (i) the complexity is dependent on the number of states in the shaping-trellis and (ii) it is compatible only with trellis shaping and cannot be combined with other shaping schemes such as the optimal shaping scheme described by the invention below. This invention describes a new precoding scheme that is simple to implement, is transparent to shaping and can be used in place of Tomlinson-Harashima precoding to realize both coding and shaping gains over ISI channels.
Prior art related to modem encoding/decoding techniques includes U.S. Pat. No. 4,731,799 of Longstaff et al. that describes a means and method to convert data by block coding. Limitations of this teaching include: (i) no provision for constrained constellation expansion ratio, (ii) it does not disclose a means or method for combining multidimensional constellation shaping with a required constant expansion ratio and (iii) no extension to trellis coded systems.
The SVQ shaping scheme for use in modems is based on a structured vector quantizer that was introduced by Laroia and Farvardin in "A Structured Fixed-Rate Vector Quantizer Derived from a Variable-Length Scalar Quantizer," submitted to IEEE Trans. Inform. Theory, August 1991). The structure of the codebook of this structured vector quantizer (SVQ) is derived from a variable-length scalar quantizer. Here, we borrow some ideas from the SVQ for the shaping of multidimensional constellations. Of particular interest in this context are the codevector encoding and decoding techniques of the SVQ. These techniques index (label) each vector of the codebook of an N-dimensional SVQ with a unique Nr-bit binary number c (codeword), where r is the rate of the SVQ in bits/sample.